package leetcode.editor.cn;

import java.util.Date;

//[198]打家劫舍
public class HouseRobber198{
public static void main(String[] args) {
   Solution solution = new HouseRobber198().new Solution();
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length < 1 )return 0;
        if (nums.length == 1 )return nums[0];
        if (nums.length == 2 )return Math.max(nums[0],nums[1]);

        //0 not steal,  1 steal
        int dp[][] = new int[nums.length][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0] ,dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }

        return Math.max(dp[nums.length-1][0],dp[nums.length-1][1]);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}